package me.mingshan.leetcode;

/**
 * 24. 两两交换链表中的节点
 *
 * https://leetcode.cn/problems/swap-nodes-in-pairs/
 *
 *
 * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,4]
 * 输出：[2,1,4,3]
 * 示例 2：
 *
 * 输入：head = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：head = [1]
 * 输出：[1]
 *
 *
 * @author hanjuntao
 * @date 2025/8/4 0004
 */
public class L_24_swap_nodes_in_pairs {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        ListNode result = swapPairs(node1);
        ListNode.print(result);

        ListNode node11 = new ListNode(1);
        ListNode node12 = new ListNode(2);
        ListNode node13 = new ListNode(3);
        ListNode node14 = new ListNode(4);
        ListNode node15 = new ListNode(5);
        ListNode node16 = new ListNode(6);
        node11.next = node12;
        node12.next = node13;
        node13.next = node14;
        node14.next = node15;
        node15.next = node16;

        ListNode result2 = swapPairs(node11);
        ListNode.print(result2);
    }

    /**
     * 思路：
     *
     * 如果要两两交交换：
     * 1. 确定要交换的节点，需要知道上一个节点与当前节点
     * 2. 进行节点交换，然后进入到下一个迭代
     *
     * 从分析看出，两个为一组，所以需要一个计数器，当前计数器累加到2时，交换当前节点与前一个节点。
     * 由于仅当前两个节点交换，不让改变值，所以需要上上个指针，用来指向新的上一个节点
     *
     *
     * 1->2->3->4->5->6
     * 2->1->4->3->6->5
     *
     *
     * @param head
     * @return
     */
    public static ListNode swapPairs(ListNode head) {
        int count = 0;

        ListNode prevPrev = null;
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            count++;
            ListNode next = curr.next;

            if (count == 2) {
                // 交换
                // 下一个节点
                if (prevPrev != null) {
                    prevPrev.next = curr;
                } else {
                    // 更新头结点
                    head = curr;
                }

                curr.next = prev;
                if (prev != null) {
                    prev.next = next;
                }

                count = 0;

                // prev 和 prevPrev 指向不做更改
                // 因为交换完之后，curr 和 prev 节点已经交换了位置
                curr = next;
            } else {
                prevPrev = prev;
                prev = curr;
                curr = next;
            }
        }

        return head;
    }

    /**
     * 递归
     *
     * 递归子问题：
     *
     * 1. 找到三个节点，节点1和节点2 进行交换，交换后，节点1的next 指向 函数处理节点3 后的头节点
     *
     * 递归终止条件：
     * 1. 必须两个节点才能进行交换，如果只有一个节点，返回当前节点
     *
     *
     * @param head
     * @return
     */
    public static ListNode swapPairs2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 1->2->3
        // 2->1->3

        ListNode node1 = head;
        ListNode node2 = head.next;
        ListNode node3 = node2.next;

        node1.next = swapPairs(node3); // 1 指向递归返回的链表头
        node2.next = node1; // 2 指向 1

        return node2; // 返回交换后的链表头节点
    }
}
